#include<iostream>
#include<vector>
using namespace std;

namespace code
{
	template<class T>
	struct greater 
	{
		bool operator()(const T& t1, const T& t2) 
		{
			return t1 > t2;
		}
	};

	template<class T>
	struct less
	{
		bool operator()(const T& t1, const T& t2)
		{
			return t1 <  t2;
		}
	};

	//小根堆
	template<class T, class Continer = vector<T>, class cmp = greater<T>>
	class priority_queue 
	{
	public:
		void AddjustUp(size_t child) 
		{
			int parent = (child - 1) / 2;
			while (child > 0) 
			{
				if (cmp()(v[parent],v[child]))
				{
					swap(v[parent], v[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else break;
			}
		}

		void AddjustDown(size_t parent)
		{
			size_t child = parent * 2 + 1;
			//调整
			while (child < v.size()) 
			{
				//选择更小的子节点
				if (child + 1 < v.size() && cmp()(v[child], v[child + 1]))child++;

				if (cmp()(v[parent], v[child]))
				{
					swap(v[parent], v[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else break;
			}
		}

		priority_queue(){}
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		:v(first, last) 
		{
			//从第一个非叶子节点开始建堆
			int n = v.size();
			for (int i = (n - 1 - 1) / 2; i >= 0; i--) 
			{
				AddjustDown(i);
			}
		}

		bool empty() const { return v.empty(); }
		size_t size() const { return v.size(); }
		const T& top() const { return v[0]; }

		void push(const T& x) 
		{
			v.push_back(x);
			AddjustUp(v.size()-1);
		}

		void pop()
		{
			size_t n = v.size();
			swap(v[0], v[n-1]);
			v.pop_back();

			AddjustDown(0);
		}

	private:
		Continer v;
	};

	void test1()
	{
		cout << "小根堆: ";
		priority_queue<int> heap;
		heap.push(4); heap.push(1); heap.push(3); heap.push(2);
		while (heap.size()) 
		{
			int top = heap.top();
			heap.pop();
			cout << top << " ";
		}

		cout << "大根堆: ";
		priority_queue<int,vector<int>, less<int>> heap2;
		heap2.push(4); heap2.push(1); heap2.push(3); heap2.push(2);
		
		while (heap2.size())
		{
			int top2 = heap2.top();
			heap2.pop();
			cout << top2 << " ";
		}

		cout << endl; cout << "迭代器区间构造" << endl;
		vector<int> v{ 1,2,3,4 };
		priority_queue<int, vector<int>, less<int>> heap3(v.begin(), v.end());
		while (heap3.size())
		{
			int top3 = heap3.top();
			heap3.pop();
			cout << top3 << " ";
		}
	}
}